package com.chen.demo.javase.algorithm;

import java.util.PriorityQueue;

/**
 * 常见排序算法
 *
 * @author chenhongwei
 * @date 2020/4/30 11:31
 **/
public class Sort {

    public static void main(String[] args) {
        int[] array = {1, 32, 12, 23, 12, 89, 12};
        mergeSort(array, 0, array.length - 1);
        System.out.println(array);

        int[] quickSortArray = {1, 32, 12, 23, 12, 89, 12};
        quickSort(quickSortArray, 0, quickSortArray.length - 1);
        System.out.println(quickSortArray);

        int[] array3 = {1, 32, 12, 23, 12, 89, 12};
        sortByPriorityQueue(array3);

        int[] array4 = {1, 32, 12, 23, 12, 89, 12};

        heapSort(array4);
        System.out.println("");
    }


    /**
     * 堆排序
     *
     * @param array array
     */
    private static void heapSort(int[] array) {
        //1.构建大根堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heapify(array, i, array.length - 1);
        }
        // 2.此处堆的根节点已经属于最大
        for (int i = array.length - 1; i > 0; i--) {

            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //再次调整堆，与第一次不同的是，这次从根节点开始调
            heapify(array, 0, i - 1);
        }


    }

    /**
     * 调整堆 注第一次调整堆的不同
     *
     * @param array       数组
     * @param parentIndex 堆调整的开始位置
     * @param endIndex    数组的最大存储元素索引
     */
    private static void heapify(int[] array, int parentIndex, int endIndex) {
        int leftIndex = 2 * parentIndex + 1;
        //加循环，注意是第一次堆的调整还是非第一次堆的调整
        while (leftIndex <= endIndex) {
            int rightIndex = leftIndex + 1;
            if (rightIndex <= endIndex && array[rightIndex] > array[leftIndex]) {
                //leftindex再赋予一层含义，即是左子树下标，又是以parent为根的树最大的值
                leftIndex++;
            }
            //根最大，不需要再调整
            if (array[parentIndex] >= array[leftIndex]) {
                break;
            }
            if (array[parentIndex] < array[leftIndex]) {
                int temp = array[leftIndex];
                array[leftIndex] = array[parentIndex];
                array[parentIndex] = temp;
                parentIndex = leftIndex;
            }
            leftIndex = 2 * parentIndex + 1;
        }
    }


    private static void sortByPriorityQueue(int[] array) {
        //
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int i : array) {
            priorityQueue.add(i);
        }
        int loop = 0;
        while (loop < priorityQueue.size()) {
            array[loop] = priorityQueue.poll();
            loop++;
        }
    }


    /**
     * 快速排序
     *| 2 | 6 | 4 | 8 | 9 | 10 | 3 |
     *
     *|
     * @param array 数组
     * @param left  数组起始位置
     * @param right 数组结束位置
     */
    private static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //分区，选择中间
        int partition = partition(array, left, right);
        //剩下没有排序的再次调用快排
        quickSort(array, left, partition - 1);
        quickSort(array, partition + 1, right);
    }

    /**
     * | 2 | 6 | 4 | 8 | 9 | 10 | 3 |
     * 第一次：
     * | 2 | 6 | 4 | 8 | 9 | 10 | 3 |
     * 第二次：
     * | 2 | 4 | 6 | 8 | 9 | 10 | 3 |
     *
     */
    private static int partition(int[] array, int left, int right) {
        // 以最后一个数据为准，小于它的依此放在前面
        // pivot 记录基准值
        int pivot = right;
        int count = left;
        int temp;
        while (left < right - 1) {
            // 比基准小，放到前面
            if (array[left] < array[pivot]) {
                temp = array[count];
                array[count] = array[left];
                array[count] = temp;
                count++;
            }
            left++;
        }
        temp = array[pivot];
        array[pivot] = array[count];
        array[count] = temp;
        return count;
    }


    /**
     * 归并排序
     *
     * @param arrays 数组
     * @param left   left
     * @param right  right
     */
    private static void mergeSort(int[] arrays, int left, int right) {
        //只有一个元素，不需再分
        if (left >= right) {
            return;
        }
        int middle = (left + right) >> 1;
        //数组再拆分
        mergeSort(arrays, left, middle);
        mergeSort(arrays, middle + 1, right);
        //合并
        merge(arrays, left, middle, right);
    }


    private static void merge(int[] array, int left, int middle, int right) {
        int leftIndex = left;
        int rightIndex = middle + 1;
        int tempIndex = 0;
        //建立临时数组
        int[] tempArray = new int[right - left + 1];

        //合并数组，
        while (leftIndex <= middle && rightIndex <= right) {
            //升序，小的先赋值
            tempArray[tempIndex++] = array[leftIndex] > array[rightIndex] ? array[rightIndex++] : array[leftIndex++];
        }
        while (leftIndex <= middle) {
            tempArray[tempIndex++] = array[leftIndex++];
        }
        while (rightIndex <= right) {
            tempArray[tempIndex++] = array[rightIndex++];
        }
        System.arraycopy(tempArray, 0, array, left, tempArray.length);
    }

}
